梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）
动态规划的本质：它是一种 “以空间换时间”的优化算法，核心是把复杂问题拆解为多个重叠的子问题，通过记录子问题的最优解（状态），避免重复计算，最终由子问题的最优解推导出原问题的最优解。
字符串问题是解决字符串的匹配、编辑、分割等问题，比如求最长回文子串、最小编辑距离、判断子序列等。这类问题的状态通常定义为两个字符串的下标 / 单个字符串的区间，状态转移依赖于字符的匹配情况，属于二维 DP 的高频应用。
问题描述：
算法解析：
#include <iostream>
#include <vector>
using namespace std;
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
// 定义dp数组：dp[i][j]表示word1前i个字符转word2前j个字符的最少操作数
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 初始化：空字符串转word2前j个字符，需要插入j次
for (int j = 0; j <= n; ++j) {
dp[0][j] = j;
}
// 初始化：word1前i个字符转空字符串，需要删除i次
for (int i = 0; i <= m; ++i) {
dp[i][0] = i;
}
// 状态转移
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
// 字符相等，无需操作，继承子问题结果
dp[i][j] = dp[i - 1][j - 1];
} else {
// 字符不等，取替换、删除、插入的最小值 + 1
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
}
// 返回最终结果
return dp[m][n];
}
int main() {
// 测试用例1：word1="horse", word2="ros"，预期输出3
cout << minDistance("horse", "ros") << endl;
// 测试用例2：word1="intention", word2="execution"，预期输出5
cout << minDistance("intention", "execution") << endl;
// 测试用例3：空字符串转换，预期输出2
cout << minDistance("", "ab") << endl;
return 0;
}
3
5
2
问题描述：
算法解析：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string longestPalindrome(string s) {
int n = s.size();
if (n <= 1) return s;
// dp[i][j]：s[i...j] 是否为回文子串
vector<vector<boo>> dp(n, vector<bool>(n, false));
int start = 0; // 最长回文子串的起始下标
int maxLen = 1; // 最长回文子串的长度（初始为1，因为单个字符都是回文）
// 初始化：长度为1的子串都是回文
for (int i = 0; i < n; ++i) {
dp[i][i] = true;
}
// 初始化：长度为2的子串
for (int i = 0; i < n - 1; ++i) {
if (s[i] == s[i+1]) {
dp[i][i+1] = true;
start = i;
maxLen = 2;
}
}
// 遍历长度 >=3 的子串，l 表示子串长度
for (int l = 3; l <= n; ++l) {
// i 是子串起始下标，j 是子串结束下标（j = i + l - 1）
for (int i = 0; i + l - 1 < n; ++i) {
int j = i + l - 1;
// 状态转移：两端字符相等，且中间子串是回文
if (s[i] == s[j] && dp[i+1][j-1]) {
dp[i][j] = true;
// 更新最长回文子串
if (l > maxLen) {
start = i;
maxLen = l;
}
}
}
}
// 截取最长回文子串
return s.substr(start, maxLen);
}
int main() {
cout << longestPalindrome("babad") << endl; // 输出 bab 或 aba（均正确）
cout << longestPalindrome("cbbd") << endl; // 输出 bb
cout << longestPalindrome("a") << endl; // 输出 a
return 0;
}
bab
bb
a
问题描述：
算法解析：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countSubstrings(string s) {
int n = s.size();
if (n == 0) return 0;
// dp[i][j]：s[i...j] 是否为回文子串
vector<vector<bool>> dp(n, vector<bool>(n, false));
int count = 0; // 统计回文子串总数
// 初始化：长度为1的子串（所有单个字符都是回文）
for (int i = 0; i < n; ++i) {
dp[i][i] = true;
count++; // 每个长度为1的子串计1个
}
// 初始化：长度为2的子串
for (int i = 0; i < n - 1; ++i) {
if (s[i] == s[i+1]) {
dp[i][i+1] = true;
count++; // 符合条件的长度为2的子串计1个
}
}
// 遍历长度 >=3 的子串，l 表示子串长度
for (int l = 3; l <= n; ++l) {
// i 是子串起始下标，j = i + l - 1 是结束下标
for (int i = 0; i + l - 1 < n; ++i) {
int j = i + l - 1;
// 状态转移：两端字符相等 + 中间子串是回文
if (s[i] == s[j] && dp[i+1][j-1]) {
dp[i][j] = true;
count++; // 符合条件的子串计1个
}
}
}
return count;
}
int main() {
cout << countSubstrings("abc") << endl; // 输出 3（a、b、c）
cout << countSubstrings("aaa") << endl; // 输出 6（a1、a2、a3、a1a2、a2a3、a1a2a3）
cout << countSubstrings("abba") << endl; // 输出 6（a、b、b、a、bb、abba）
return 0;
}
3
6
6
问题描述：
算法解析：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
// dp[i][j]：s前i个字符和p前j个字符是否匹配
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true; // 空字符串匹配空模式
// 初始化：空字符串匹配带*的模式（处理p以a*、a*b*开头的情况）
for (int j = 2; j <= n; ++j) {
if (p[j-1] == '*') {
dp[0][j] = dp[0][j-2];
}
}
// 状态转移
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j-1] == '.' || s[i-1] == p[j-1]) {
// 场景1：普通字符/'.' 匹配
dp[i][j] = dp[i-1][j-1];
} else if (p[j-1] == '*') {
// 场景2：'*' 匹配，先考虑匹配零次的情况
dp[i][j] = dp[i][j-2];
// 再考虑匹配至少一次的情况（需前面字符匹配）
if (p[j-2] == '.' || s[i-1] == p[j-2]) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
// 其他情况：默认false
}
}
return dp[m][n];
}
int main() {
// 测试用例1：s="aa", p="a" → false（需完全匹配）
cout << boolalpha << isMatch("aa", "a") << endl;
// 测试用例2：s="aa", p="a*" → true（*匹配多个a）
cout << boolalpha << isMatch("aa", "a*") << endl;
// 测试用例3：s="ab", p=".*" → true（.*匹配任意字符任意次数）
cout << boolalpha << isMatch("ab", ".*") << endl;
// 测试用例4：s="aab", p="c*a*b" → true（c*匹配0次，a*匹配2次）
cout << boolalpha << isMatch("aab", "c*a*b") << endl;
return 0;
}
false
true
true
true